2022-11-07

Agenda

  • Entstehung
  • Standard PSO
  • Beispiel 2D
  • Nebenbedingungen
  • Beispiel 2D mit Nebenbedingungen
  • Konvergenz
  • Vor- und Nachteile
  • Fazit

Entstehung

  • Erfunden von Russell Eberhardt und James Kennedy in 1995
  • Analogie zu natürlichen Vogelschwärmen
  • PSO ist eine naturanaloge Metaheuristik
  • Erste Anwendung in der Teilchenphysik

Partikelschwarmoptimierung Grundlagen

Optimierungsproblem:

  • Lösungsraum \(\Omega\) (z.b. \(\mathbb{R}^n\))
  • Zielfunktion: \(f: \Omega \rightarrow \mathbb{R}\)
  • Gesucht ist \(\omega \in \Omega\) für das \(f(\omega) = min\{f(x)|x \in \Omega\}\) gilt

Vehalten des PSO:

  • Partikel bewegen sich im \(\mathbb{R}^n\) iterativ
  • Partikel teilen sich Informationen
  • Partikel haben ein Gedächtnis
  • Partikel ändern ihren Richtungsvektor abhängig von 3 Faktoren
  • Iteriere bis die Abbruchbedingung erreicht ist

Standard PSO (SPSO)

  1. Initialisiere zufällige Positionen \(x^{k, i}\) und Richtungsvektoren \(v^{k, i}\) der Partikel \(k\) in Iteration \(i=0\)

  2. Evaluiere die Kostenfunktion mit der Position jedes Partikels

  3. Speicher die bisher beste Position pro Partikel in \(p_{best}^{k,i}\)

  4. Speicher die bisher beste Position aller Partikel in \(g_{best}^i\)

  5. Iterationsschritt \(i \rightarrow i+1\) pro Partikel \(k\): \[ \begin{aligned} v^{k, i+1} &= w \cdot v^{k, i} + c_p \cdot r_1^{k,i} \cdot (p_{best}^{k,i}-x^{k,i}) + c_g \cdot r_2^{k,i} \cdot (g_{best}^{k,i}-x^{k,i}) \\ x^{k, i+1} &= x^{k, i} + v^{k, i+1} \end{aligned} \]

  6. Wiederhole Schritt 2-5 bis die Abbruchbedingung erreicht ist

SPSO Zeitschritt

\[ \begin{aligned} v^{k, i+1} &= w \cdot v^{k, i} + c_p \cdot r_1^{k,i} \cdot (p_{best}^{k,i}-x^{k,i}) + c_g \cdot r_2^{k,i} \cdot (g_{best}^{k,i}-x^{k,i}) \\ x^{k, i+1} &= x^{k, i} + v^{k, i+1} \end{aligned} \]

Einfaches Beispiel

Zielfunktion:
\[ \begin{aligned} f(x, y) =& -20\cdot e^{-0.2 \cdot \sqrt{0.5 \cdot ((x-1)^2 + (y-1)^2)}} \\ & \ - e^{0.5 \cdot ( cos(2\cdot \pi \cdot x) + cos(2\cdot \pi \cdot y))} + e + 20 \end{aligned} \] Aufgabe:
Minimiere \(f(x,y)\) mit \(-10 \leq x \leq 10\) und \(-10 \leq y \leq 10\)

PSO App

Nebenbedingungen

Beispiele:

  • Summe soll 100% ergeben
  • Summe der Gewichte von Elementen mit Ausprägung A soll weniger als 20% betragen
  • Kosten sollen kleiner als 100 Euro sein
  • Weniger als 20 Elemente sollen ungleich Null sein
  • …

Methoden:

  • Penalty
  • Verwerfen von ungültigen Lösungen
  • Reparieren von ungültigen Lösungen

Penalty Methode

Alte Zielfunktion: \(f(x)\) mit \(f: \mathbb{R}^n \rightarrow \mathbb{R}\)

Bruch von Nebenbedingungen: \(g(x)\) mit \(g(x) \geq 0 \ \forall x \in \mathbb{R}^n\)

Neue Zielfunktion: \(z(x) = f(x) + g(x)\)


Beispiel für gängige Nebenbedingungen: \[ A^T \times x \geq b_0 \] Dann könnte \(g(x)\) wie folgt aussehen: \[ g(x) = ||\vec{\lambda}( A^T \times x - b_0 )||_2^2 \] mit elementweiser Anwendung von \[ \lambda(x) = \begin{cases} 0 &\text{ if }x \geq 0\\ x &\text{ if }x < 0 \end{cases} \]

Penalty Methode Beispiel 2D

Konvergenz

Convergence Analysis for Particle Swarm Optimization (von Berthold Schmitt)

“Obwohl das PSO in zahlreichen realen Anwendungen verwendet wird, haben theoretische Betrachtungen bisher nur einige wenige Teilaspekte des Algorithmus erklärt. Ein solcher Aspekt, mit dem sich viele Wissenschaftler auseinandersetzen, ist das Phänomen der Konvergenz des Partikelschwarms. Das bedeutet, dass die Partikel gegen einen Punkt im Suchraum konvergieren. Insbesondere konnten notwendige und hinreichende Bedingungen an die Schwarmparameter ermittelt werden, unter denen Konvergenz gewährleistet ist. Allerdings ist bis jetzt kein theoretisches Resultat über die Qualität dieses Grenzwertes bekannt, das für den unmodizierten PSO-Algorithmus in einer allgemeineren Situation als beispielsweise nur für genau eine Zielfunktion bewiesen werden konnte.”

  • Alles stark simplifiziert: Standard PSO und \(p_{best}=g_{best}=const\)
  • Es kann gezeigt werden, das folgende Terme konvergieren: \(\lim\limits_{n \rightarrow \infty}E(X^n)=\mu\) und \(\lim\limits_{n \rightarrow \infty}Var(X^n) = \sigma^2\)
  • Es kann keine Aussage über die Qualität dieses Grenzwertes gemacht werden.
  • Es kann bewiesen werden, das wenn der Schwarm im \(\mathbb{R}\) konvergiert, das es fast sicher ein locales Minimum ist.

Interpretation der Aussagen

Einschränkung: \(p_{best}\) und \(g_{best}\) sind konstant

Folgerung: Partikel sind unabhängig

\[ \begin{aligned} v^{i+1} &= w \cdot v^{i} + c_p \cdot r_1^{i} \cdot (p_{best}^{i}-x^{i}) + c_g \cdot r_2^{i} \cdot (g_{best}^{i}-x^{i}) \\ x^{i+1} &= x^{i} + v^{i+1} \end{aligned} \] Theorem 1: Gegeben \(w\), \(c_p\), \(c_g \geq 0\) und es gilt \(0 \leq w <1\) und \(0 < c_p + c_g < 4\cdot(1+w)\) dann konvergiert der iterative Prozess \(E(x^i)_{i \in \mathbb{N}}\) fast sicher gegen \[ \mu := \frac{c_p \cdot p_{best} + c_g \cdot g_{best}}{c_p +c_g} \]

Theorem 2: Gegeben \(w\), \(c_p\), \(c_g \geq 0\) und es gilt \(0 \leq w <1\), \(c_p + c_g > 0\) und \(g>0\) mit \[ g := 1-((1+w-\frac{c_p+c_g}{2})^2+\frac{1}{12}\cdot (c_p^2+c_g^2)-w)\cdot (1-w)-w^3 \] dann konvergiert der iterative Prozess \(Var(x^i)_{i \in \mathbb{N}}\) fast sicher gegen \[ \sigma^2 := \frac{1}{6} \cdot (\frac{c_p \cdot c_g}{c_p + c_g})^2\cdot (g_{best}-p_{best})^2\cdot (1-w) / g \]

Konvergenz Beispiel 1D

  • Konstantes \(p_{best}=5\) und \(g_{best}=7\)
  • Partikel sind unabhängig
  • Hyperparameter \(w=0.3\), \(c_p=1\), \(c_g=1\)
  • Initialisierte Position und Richtungsvektor \(X^0=V^0=0\)

\(f=\) 0.9033333

Vor- und Nachteile

Nachteile:

  • keine Garantie für die Qualität der Lösung
  • Hyperparameter
  • zusätzliche Information über das explizite Problem kann nur schwer berücksichtigt werden

Vorteile:

  • ist sehr effizient implementierbar (kleine Datenstruktur und nur Basis-Operatoren)
  • simple Anwendbar auch bei komplexen Problemen und Nebenbedingungen
  • kann diskrete Probleme lösen
  • es gibt viele Varianten, die deutlich besser sind als das Standard PSO
  • Allzweck-Werkzeug für Optimierungsprobleme

Fazit

PSO nur verwenden, wenn keine analytische Lösung möglich ist oder diese zu aufwändig wäre